{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. _nb_brkga:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# BRKGA: Biased Random Key Genetic Algorithm\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An excellent and very informative presentation about BRKGAs can be found [here](http://mauricio.resende.info/talks/2012-09-CLAIO2012-brkga-tutorial-both-days.pdf). BRKGAs are known to perform well-known on combinatorial problems."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: center;\">\n",
    "    <img src=\"https://github.com/anyoptimization/pymoo-data/blob/main/docs/images/brkga.png?raw=true\" width=\"350\">\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of customizing evolutionary operators, decoding has to be defined. Therefore, evolution takes place solely on real-valued variables. \n",
    "\n",
    "Let us define a permutation problem which derives an order by sorting real-valued variables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "from pymoo.core.problem import ElementwiseProblem\n",
    "\n",
    "\n",
    "class MyProblem(ElementwiseProblem):\n",
    "\n",
    "    def __init__(self, my_list):\n",
    "        self.correct = np.argsort(my_list)\n",
    "        super().__init__(n_var=len(my_list), n_obj=1, n_ieq_constr=0, xl=0, xu=1)\n",
    "\n",
    "    def _evaluate(self, x, out, *args, **kwargs):\n",
    "        pheno = np.argsort(x)\n",
    "        out[\"F\"] = - float((self.correct == pheno).sum())\n",
    "        out[\"pheno\"] = pheno\n",
    "        out[\"hash\"] = hash(str(pheno))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since duplicate eliminates is an essential aspect for evolutionary algorithms, we have to make sure all duplicates with respect to the permutation (and not to the real values) are filtered out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from pymoo.core.duplicate import ElementwiseDuplicateElimination\n",
    "\n",
    "\n",
    "class MyElementwiseDuplicateElimination(ElementwiseDuplicateElimination):\n",
    "\n",
    "    def is_equal(self, a, b):\n",
    "        return a.get(\"hash\") == b.get(\"hash\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we define a problem that has to sort a list by their values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(2)\n",
    "list_to_sort = np.random.random(20)\n",
    "problem = MyProblem(list_to_sort)\n",
    "print(\"Sorted by\", np.argsort(list_to_sort))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we use `BRKGA` to obtain the sorted list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from pymoo.algorithms.soo.nonconvex.brkga import BRKGA\n",
    "from pymoo.optimize import minimize\n",
    "\n",
    "algorithm = BRKGA(\n",
    "    n_elites=200,\n",
    "    n_offsprings=700,\n",
    "    n_mutants=100,\n",
    "    bias=0.7,\n",
    "    eliminate_duplicates=MyElementwiseDuplicateElimination())\n",
    "\n",
    "res = minimize(problem,\n",
    "               algorithm,\n",
    "               (\"n_gen\", 75),\n",
    "               seed=1,\n",
    "               verbose=False)\n",
    "\n",
    "print(\"Best solution found: \\nX = %s\\nF = %s\" % (res.X, res.F))\n",
    "print(\"Solution\", res.opt.get(\"pheno\")[0])\n",
    "print(\"Optimum \", np.argsort(list_to_sort))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### API"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. autoclass:: pymoo.algorithms.soo.nonconvex.brkga.BRKGA\n",
    "    :noindex:"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
